'''
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

'''


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        #有点不太熟悉，多看几遍
        
        
        #数组长度
        n =len(nums)
        
        #如果长度不够4，则直接返回为空数组
        if n<4:
            return []
        
        #对数组进行排序
        nums.sort()
        
        #待返回的数组
        rlist=[]
        
        
        for i in range(n-3):#因为j是i+1,l是j+1,因此需要空出来2+1个位置
            for j in range(i+1,n-2):#因为l是j+1,因此需要空出来1+1个位置
                l = j+1
                r = n-1

                while(l<r):
                    sum = nums[i]+nums[j]+nums[l]+nums[r]
                    if sum>target:
                        r -=1
                    elif sum<target:
                        l +=1
                    elif sum==target:
                        tar  =[nums[i],nums[j],nums[l],nums[r]]
                        if tar not in rlist:
                            rlist.append(tar)
                        l +=1
                        r -=1
                         
        return rlist